package com.acwing.partition11;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/25 14:12
 */
public class AC1084数字游戏II {

    private static final int N = 11, P = 101;
    //dp[i][j][k]表示高位是1，长度为j的数字和p取模为k的方案数，(各位数字之和+k)%p=0
    private static int[][][] dp = new int[10][N][P];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        while (true) {
            String s = reader.readLine();
            if (s == null || s.isEmpty()) break;
            String[] str = s.split("\\s+");
            int a = Integer.parseInt(str[0]), b = Integer.parseInt(str[1]), n = Integer.parseInt(str[2]);
            //模数是变化的，每次都需要进行初始化
            init(n);
            writer.write((resolve(b, n) - resolve(a - 1, n)) + "\n");
        }
        writer.flush();
    }

    private static void init(int p) {
        //初始化出模数范围内的数值，如果预处理出所有的模数就只需要初始化一次
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 10; j++) {
                for (int k = 0; k < p; k++) dp[i][j][k] = 0;
            }
        }
        for (int i = 0; i <= 9; i++) dp[i][1][i % p]++;
        //当前高位为i，所有数字位总和为sum，则余数k=(i+sum)%p => (i+sum)%p=k%p => sum%p=(k-i)%p
        for (int length = 2; length < N; length++) {
            for (int i = 0; i <= 9; i++) {
                for (int k = 0; k < p; k++) {
                    for (int j = 0; j <= 9; j++) {
                        dp[i][length][k] += dp[j][length - 1][mod(k - i, p)];
                    }
                }
            }
        }
    }

    private static int resolve(int num, int p) {
        if (num == 0) return 1;
        List<Integer> nums = new ArrayList<>();
        while (num != 0) {
            nums.add(num % 10);
            num /= 10;
        }
        //这里的last记录的是截止当前，每位的数位之和
        int answer = 0, last = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            //关系式 (last+s)%p=k，k为余数，last表示当前i位前的所有和，s表示之后的所有和，要满足余数为0，也即(last+s)%p=0 => s=-last
            for (int j = 0; j < x; j++) answer += dp[j][i + 1][mod(-last, p)];
            last += x;
            //如果遍历到最后，当前数字num的每一位刚好也满足条件，进行加1
            if (i == 0 && last % p == 0) answer++;
        }
        return answer;
    }

    private static int mod(int x, int m) {
        return (x % m + m) % m;
    }
}
